﻿#pragma once
#include "FormatedUtil.h"
#include "Index.h"
class IFindMedianSortedArrays
{
public:
	/**
	 * 寻找两个正序数组的中位数.
	 *
	 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
	 * 算法的时间复杂度应该为 O(log (m+n)) 。
	 *
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode.cn/problems/median-of-two-sorted-arrays
	 */
	virtual double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) = 0;
};

class FindMedianSortedArrays
{
public:
	class BinarySearch:public IFindMedianSortedArrays
	{
		friend class FindMedianSortedArraysTest;
	public:
		double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) override
		{
			const int numsSize = nums1.size() + nums2.size();
			if (numsSize == 0)
				return 0;

			const double midVal=findKthInSortedArrays(nums1, 0, nums1.size() - 1, nums2, 0, nums2.size() - 1, numsSize >> 1);
			//总的数组元素数量为奇数
			if ((numsSize & 0x1) == 1)
				return midVal;
			//总的数组元素数量为偶数
			const double midRightVal = findKthInSortedArrays(nums1, 0, nums1.size() - 1, nums2, 0, nums2.size() - 1, (numsSize >> 1) - 1);
			return (midVal + midRightVal) / 2.0;
		}
	private:
		int findKthInSortedArrays(std::vector<int>& nums1,int left1,int right1,
								std::vector<int>& nums2,int left2,int right2,
								int kth)
		{
			const bool nums1Invalid = left1 > right1;
			const bool nums2Invalid = left2 > right2;
			DEV_ASSERT_BREAK(!(nums1Invalid && nums2Invalid));

			if (nums1Invalid)
				return nums2[left2+kth];
			if (nums2Invalid)
				return nums1[left1+kth];

			const int nums1Size = right1 - left1 + 1;
			const int nums2Size = right2 - left2 + 1;
			//在数组1中随机选择一个数字作为pivot
			{
				const int pivotIndex = left1+(std::rand() % nums1Size);
				const int& pivot = nums1[pivotIndex];

				//满足nums2[pivotIndexAnother]>=pivot的索引位置
				int pivotIndexAnother = right2+1;
				//pivot在另外一个数组的大小顺序
				int left = left2, right = right2;
				while(left<=right)
				{
					const int midIndex = (left + right)>>1;
					const int mid = nums2[midIndex];
		
					if (mid == pivot)
					{
						pivotIndexAnother = midIndex;
						break;
					}
					else if (mid > pivot)
					{
						pivotIndexAnother = midIndex;
						right = midIndex - 1;
					}
					else
						left = midIndex + 1;
				}

#ifdef DEV_TEST
				if(pivotIndexAnother>right2)
				{
					DEV_ASSERT_BREAK(nums2[right] < pivot);
				}
				else
				{
					DEV_ASSERT_BREAK(nums2[pivotIndexAnother] >= pivot);
				}
#endif

				//由pivotIndex和pivotIndexAnother可以知道pivot在两个升序的数组中排在第几大
				int pivotOrder = 0;
				pivotOrder += pivotIndex - left1;
				pivotOrder += pivotIndexAnother - left2;

				if (pivotOrder == kth)
					return pivot;
				else if(pivotOrder<kth)
				{
					left1 = pivotIndex + 1;
					left2 = pivotIndexAnother;
					kth -= pivotOrder+1;
				}
				else
				{
					right1 = pivotIndex - 1;
					right2 = pivotIndexAnother - 1;
				}
				return findKthInSortedArrays(nums1, left1, right1, nums2, left2, right2, kth);
			}
		}
	};
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
class FindMedianSortedArraysTest:public SolutionTestor<IFindMedianSortedArrays>
{
protected:
	void LoadSolutions(std::vector<IFindMedianSortedArrays*>& solutions) override
	{
		solutions = {
			new FindMedianSortedArrays::BinarySearch,
		};
	}

	int findKthInSortedArrays(FindMedianSortedArrays::BinarySearch solution, std::vector<int>& nums1, int left1, int right1,
		std::vector<int>& nums2, int left2, int right2,
		int kth)
	{
		return solution.findKthInSortedArrays(nums1, left1, right1, nums2, left2, right2, kth);
	}
};

TEST_F(FindMedianSortedArraysTest, findMedianSortedArrays)
{
	TestForSolutions([](IFindMedianSortedArrays* solution)
		{
			const std::vector<std::vector<std::string>> testCases = {
				{"[1,3]", "[2]"},
				{"[1,3]", "[2,4]"},
				{"[7,7]", "[7,7,7,7]"},
				{"[]", "[1,2,3,5,6]"},
				{"[1,2,6,9]", "[]"},
				{"[]", "[]"},
				{"[1,4,6,7,7,7,7,9,12,20]", "[1,2,3,5,7,7,7,7,7,16]"}
			};

			for(auto testCase :testCases)
			{
				std::vector<int> nums1, nums2;
				FormatedUtil::parseFormated(nums1, testCase[0]);
				FormatedUtil::parseFormated(nums2, testCase[1]);

				double expectResult = 0;
				std::vector<int> nums;
				nums.insert(nums.end(), nums1.begin(), nums1.end());
				nums.insert(nums.end(), nums2.begin(), nums2.end());
				std::sort(nums.begin(), nums.end());
				if(!nums.empty())
				{
					const int mid = nums.size() >> 1;
					if ((nums.size() & 0x1) == 1)
						expectResult = nums[mid];
					else
						expectResult = (nums[mid - 1] + nums[mid]) / 2.0;
				}

				auto result= solution->findMedianSortedArrays(nums1, nums2);
				EXPECT_EQ(result, expectResult);
			}
		});
}
TEST_F(FindMedianSortedArraysTest, findKthInSortedArrays)
{
	FindMedianSortedArrays::BinarySearch solution;

	//不含重复数字的递增数组
	{
		std::vector<int> nums1 = { 2,3,6,7,8 };
		std::vector<int> nums2 = { 1,4,5,9 };
		for (int i = 0; i < 9; ++i)
		{
			auto result = findKthInSortedArrays(solution, nums1, 0, nums1.size() - 1,
				nums2, 0, nums2.size() - 1, i);
			EXPECT_EQ(result, i + 1);
		}
	}

	//含有重复数字的递增数组
	{
		std::vector<int> nums1 = { 2,3,6,7,7 };
		std::vector<int> nums2 = { 1,7,7,9 };

		std::vector<int> nums;
		nums.insert(nums.end(), nums1.begin(), nums1.end());
		nums.insert(nums.end(), nums2.begin(), nums2.end());
		std::sort(nums.begin(), nums.end());

		for (int i = 0; i < nums.size(); ++i)
		{
			auto result = findKthInSortedArrays(solution, nums1, 0, nums1.size() - 1,
				nums2, 0, nums2.size() - 1, i);
			EXPECT_EQ(result, nums[i]);
		}
	}
}
#endif